#include <iostream>

using namespace std;

/*
Given a simplified version of regular expressions, implement a function which will 
match a pattern against a string and return true or false depending on whether or 
not they match.

Pattern Syntax:
'.' Match any character at that position in the subject string
'*' Match any zero or many characters combinations 

Any other character matches its exact value only (case sensitive)
*/

//
// String: input string to match
// Pattern: the pattern string 
//
bool WildCardMatching( char *String, char *Pattern )
{
	if( !String || !Pattern )
		return false;
	else if( !*String || !*Pattern )
		return (*String == *Pattern);

	while( *String && *Pattern )
	{
		switch( *Pattern )
		{
		case '.':
			break;
		case '*':
			return ( WildCardMatching( String, Pattern+1) ||
					 WildCardMatching( String+1, Pattern) ||
				     !*(Pattern+1) );
		default:
			if( *String != *Pattern )
				return false;
		}
		String++;
		Pattern++;
	}

	if( *String )
		return false;

	while( *Pattern == '*' )
		Pattern++;

	return !(*Pattern);
}

bool isMatched( char str, char pattern)
{
	if( str == pattern ||
		(str != '\0' && pattern == '.') )
	{
		return true;
	}
	return false;
}

bool WildCardMatching2( char *String, char *Pattern )
{
	if(*Pattern=='\0') 
		return (*String=='\0');
	
	if( *Pattern != '*')
	{
		if(isMatched(*String, *Pattern))
		{
			return WildCardMatching2( String+1, Pattern+1);
		}
		return false;
	}

	while( *String != '\0') 
	{
		if(WildCardMatching2(String, Pattern+1)) 
			return true;
		String++;
	}

	return false;
}

typedef struct _STRINGS{
	char * String;
	char * Pattern;
	bool IsMatch;
} STRING, *PSTRING;

int const EntryCount = 8;
STRING TestStrings[EntryCount]=
{
	{"abcdefg", "a*", true},
	{"abcdefg", "*b", false},
	{"abcdefg", "*g", true},
	{"abcdefg", "abcdefg*", true},
	{"abcdefg", "abcdefg", true},
	{"abcdefg", "abcdefgh", false},
	{"abcdefg", "abcde******", true},
	{"abcdefg", "a..d*", true}
};

int main()
{
	bool succeed= true;
	for( int i=0; i<EntryCount; i++ )
	{
		if( WildCardMatching(TestStrings[i].String, TestStrings[i].Pattern ) != TestStrings[i].IsMatch )
		{
			if( TestStrings[i].IsMatch )
				printf("Pattern %s match string %s is expected to be TRUE\n", TestStrings[i].Pattern, TestStrings[i].String);
			else
				printf("Pattern %s match string %s is expected to be FALSE\n", TestStrings[i].Pattern, TestStrings[i].String);

			succeed= false;
		}
	}

	if( succeed )
		cout<<"Test1 succeed!!!"<<endl;

	succeed= true;
	for( int i=0; i<EntryCount; i++ )
	{
		if( WildCardMatching2(TestStrings[i].String, TestStrings[i].Pattern ) != TestStrings[i].IsMatch )
		{
			if( TestStrings[i].IsMatch )
				printf("Pattern %s match string %s is expected to be TRUE\n", TestStrings[i].Pattern, TestStrings[i].String);
			else
				printf("Pattern %s match string %s is expected to be FALSE\n", TestStrings[i].Pattern, TestStrings[i].String);

			succeed= false;
		}
	}

	if( succeed )
		cout<<"Test2 succeed!!!"<<endl;


	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}
